#include<iostream>

using namespace std;

struct ListNode{
    int value;
    ListNode * next;
};

ListNode * createNode(int * data, int length){
    if ( data == nullptr || length <= 0 )
        return nullptr;
    ListNode * head = new ListNode();
    head -> value = data[0];
    head -> next = nullptr;
    ListNode * pHead = head;
    for ( int i=1;i<length; i++ ){
        ListNode * node = new ListNode();
        node -> value = data[i];
        node -> next = nullptr;
        pHead = pHead -> next = node;
    }
    return head;
}


// 求中间节点，当链表总结点数为奇数，返回中间节点；为偶数时返回中间两个节点的任意一个。
// 解决：定义两个指针，同时出发，一个指针一次走一步，另一个指针一次走两步，当走得快的指针到达末尾，满指针正好在中间节点
ListNode * findMidNode(ListNode * head ){
	ListNode * frontNode = head;
	ListNode * tailNode = head;
	if ( head == nullptr)
		return nullptr;
	while ( frontNode != nullptr ){
		frontNode = frontNode -> next -> next;
		tailNode = tailNode -> next;
	} 
	return tailNode;

}

int main(void){
    int data[] = {1,2,3,4,5,6,7,8,9,0};
    ListNode * head = createNode(data, sizeof(data)/sizeof(int));
    ListNode * node = findMidNode(head);
    if ( node == nullptr ){
	    cout << "input param is invaild" << endl;
    }else{
        cout << node->value << endl;
    }    
    return 0;
}